/// @tags: DPwithMonotoneStack MonotoneDecision
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 1e5 + 5, M = 1e4 + 5;

int n;
int sum[N], buk[M], s[N];
LL f[N];
vector<int> stk[N];

inline LL calc(int p, int t) { return f[p - 1] + (LL)s[p] * t * t; }

inline int check(int x, int y) {
  int l = 1, r = n, mid;
  while (l < r) {
    mid = (l + r) >> 1;
    calc(x, mid - sum[x] + 1) >= calc(y, mid - sum[y] + 1) ? r = mid : l = mid + 1;
  }
  return l;
}

inline int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> s[i], sum[i] = ++buk[s[i]];
  for (int i = 1; i <= n; ++i) {
    int c = s[i];
    while (stk[c].size() >= 2 &&
           check(stk[c][stk[c].size() - 2], stk[c].back()) <= check(stk[c].back(), i))
      stk[c].pop_back();
    stk[c].push_back(i);
    while (stk[c].size() >= 2 &&
           check(stk[c][stk[c].size() - 2], stk[c].back()) <= sum[i])
      stk[c].pop_back();
    f[i] = calc(stk[c].back(), sum[i] - sum[stk[c].back()] + 1);
  }
  cout << f[n];
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P5504 [JSOI2011] 柠檬.in", "r", stdin);
  freopen("P5504 [JSOI2011] 柠檬.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
